package 链表;

public class NC50链表中每K个节点一组翻转No25 {

    /**
     * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
     * k 是一个正整数，它的值小于或等于链表的长度。
     * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     *
     * 示例：
     * 给你这个链表：1->2->3->4->5
     * 当 k = 2 时，应当返回: 2->1->4->3->5
     * 当 k = 3 时，应当返回: 3->2->1->4->5
     *
     * 说明：
     * 你的算法只能使用常数的额外空间。
     * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
     */

    public ListNode reverseKGroup(ListNode head, int k) {

        ListNode dump=new ListNode(-1);
        dump.next=head;//适配 K>节点数的情况
        ListNode last=dump;//上一个组的尾节点
        ListNode first;
        ListNode pre=head;

        while (pre!=null){

            first=pre;//当前组的头节点

            int i = 0;
            for (; i < k-1 && pre.next!=null; i++) {
                pre=pre.next;
            }
            if(i!=k-1){
                break;
            }
            //pre为当前组的最后一个节点
            ListNode next=pre.next;//下一组的头节点
            pre.next=null;//截断,便于翻转

            //翻转,返回尾节点做头节点
            ListNode listNode = reverseList(first);

            //与下一组连接上
            first.next=next;

            last.next=listNode;//上组尾连接此组

            last=first;//维护上一节点

            pre=next;//去一个头节点
        }

        return dump.next;
    }


    //来个翻转链表
    private ListNode reverseList(ListNode node){

        ListNode last=null;
        ListNode pre=node;
        ListNode next;

        while (pre!=null){
            next=pre.next;
            pre.next=last;
            last=pre;
            pre=next;
        }

        return last;
    }

    public static void main(String[] args) {
        ListNode listNode = ListNode.createListNode(new int[]{1});
        NC50链表中每K个节点一组翻转No25 n=new NC50链表中每K个节点一组翻转No25();
        ListNode result = n.reverseKGroup(listNode, 3);
        ListNode.printListNode(result);
    }



}
